package day_2022_7_to_8.day48;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 406. 根据身高重建队列
 * @author haomin
 * @date 2022/07/31 20:05
 **/
public class Day16_1_Num406_ReconstructQueue {
    class Solution {
        public int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[0] != o2[0] ? o1[0]-o2[0] : o2[1]-o1[1];
                }
            });
            int[][] res = new int[people.length][];
            for(int[] o : people){
                int index = o[1]+1;
                for(int i = 0;i < res.length;i++){
                    // 1.先填入的人的身高必定是小于当前人的升高，
                    // 2.除了先填入的人，还有o[1]个人比当前人高，且位置是null，都在当前人之前
                    // 3.所有当null位置减完后的位置就是当前人的位置
                    if(res[i] == null){
                        index--;
                        if(index == 0) {
                            res[i] = o;
                            break;
                        }
                    }
                }
            }
            return res;
        }
    }
}